\subsection*{Transposition ciphers}

\begin{proof}[\textbf{Solution~\ref{ex:classical_crypto:block_length_columnar_transposition}}]
The block length is the number of characters which are involved in each 
permutation, which equals $rs$ for an $(r,s)$-simple columnar transposition.
In terms of maps of indices, the $k$-th position maps to $(i,j)$ in an array 
where $i = ((k-1) \bmod s) + 1$ and $j = (k-1)\ {\rm div}\ s$ (for $k$ in 
$1,\dots,rs$).  
The transpose maps $(i,j)$ to $(j,i)$, which goes to the new position 
$\pi(k) = i+(j-1)r$ in the ciphertext.  The map $k \mapsto \pi(k)$ determines 
the {\it inverse} of the permutation on indices.  The inverse permutation is 
determined by exchanging the roles of $r$ and $s$.
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:classical_crypto:columnar_transposition_order_2}}]
For a $(r,r)$-simple columnar transposition one writes each $r^2$-block into 
an $r \times r$ array, applies a transposition, and reads the columns off as 
rows.  It has order $2$ since two-fold application of the cipher acts as the 
identity on every $r^2$-block.  

In general, an $(r,s)$-simple columnar tranposition cipher does not have order 
$2$ since the transpose matrix does not have the same form, so $r$ characters 
are read from each column, while $s$ characters are written into each row at 
the next application of the cipher.  The inverse of an $(r,s)$-simple 
columnar transposition is an $(s,r)$-simple columnar transposition.

The $(3,5)$-simple columnar transposition is determined by the following map 
of indices 
$$
1 \mapsto 1,\ 2 \mapsto 6,\ 3 \mapsto 11, \dots
$$
giving the map in list notation
$$
[1, 6, 11, 2, 7, 12, 3, 8, 13, 4, 9, 14, 5, 10, 15]
$$
In Sage we can construct this sequence and determine the cycle notation for 
the permuation as follows:

\input{code/solution02.5.sage}

The equivalent construction for $(r,s) = (7,36)$ follows.
\input{code/solution02.6.sage}
\end{proof}
